#include "../tools.h"
#include <stack>
using std::stack;
using std::isdigit;
using std::islower;

class Solution {
public:
    string countOfAtoms(string formula) {
        stack<unordered_map<string, int>> s;
        s.push({});
        int i = 0, n = formula.size();

        auto parseAtom = [&]() -> string{
            if(islower(formula[i])) return "error";
            string atom;
            atom += formula[i++];
            while (i < n && islower(formula[i]))
            {
                atom += formula[i++];
            }
            return atom;
        };
        
        auto parseNum = [&]() -> int{
            if(i == n || !isdigit(formula[i])){
                return 1;
            }
            int num = 0;
            while(i < n && isdigit(formula[i])){
                num = num * 10 + int(formula[i] - '0');
                ++i;
            }
            return num;
        };

        while(i < n){
            if(formula[i] == '('){
                ++i;
                // 栈压入新元素
                s.push({});
                
            }else if(formula[i] == ')'){
                ++i;
                // 出栈，与栈顶合并
                int num = parseNum();
                unordered_map<string, int> e = s.top();
                s.pop();
                for(auto& [k, v]: e){
                    s.top()[k] += v * num;
                }
            }else{
                // 填充栈顶，注意小写
                string k = parseAtom();
                int num = parseNum();
                s.top()[k] += num;
            }
        }

        unordered_map<string, int>& e = s.top();
        vector<pair<string, int>> v;
        for(pair<string, int> p: e)
            v.emplace_back(p);
        sort(v.begin(), v.end());

        string res;
        for(auto i = v.begin(); i != v.end(); ++i){
            res += i->first;
            if(i->second > 1)
                res += to_string(i->second);
        }

        return res;
    }
};

int main(int argc, char const *argv[])
{
    string formula = "K4(ON(SO3)2)2";
    
    Solution s;
    cout << s.countOfAtoms(formula);
    
    return 0;
}

